package test230602;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/6/2 12:26
 * 53. 最大子数组和
 * https://leetcode.cn/problems/maximum-subarray/
 */
public class Solution01 {

    public int maxSubArray(int[] nums) {
        int n = nums.length;
        // dp[i] 表示以 i 位置元素为结尾的所有子数组中的最大和
        int[] dp = new int[n];
        dp[0] = nums[0];
        int max = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}
